# 使用numpy模块生成随机数
import numpy as np

import time

def calcTime(func):
    '''
    函数修饰器, 用来计算算法的执行时间
    最终返回一个 list [temp, time_sum]
                    temp : 运行结果
                    time_sum : 算法执行时间(单位ms)
    '''
    def warpper(nums1,nums2,k):
        time_start = time.perf_counter()
        temp = func(nums1,nums2,k)
        time_end = time.perf_counter()
        time_sum = time_end - time_start
        return [temp, time_sum *1000]
    return warpper

# 随机生成[1,10)的长度为n的分数数组nums
def nums(n):
    nums1 = list(np.random.randint(1, 10, size=n))
    nums2 = list(np.random.randint(1, 10, size=n-2))
    return [nums1,nums2]

@calcTime
def maxNumber(nums1, nums2, k):  # 从0到k遍历各自数组中找出最大的子序列,再合并成一个大的子序列,比较出最终的最大合并子序列
    def pick_k_max(nums, k):     # 从数组中选出k位最大的数
        stack = []
        remain_num = len(nums) - k
        for num in nums:
            while remain_num and stack and stack[-1] < num:
                stack.pop()
                remain_num -= 1
            stack.append(num)
        return stack[:k]

    def merge(A, B):             # 合并两个数组,组成一个大的数组
        res = []
        while A or B:
            bigger = A if A > B else B
            res.append(bigger[0])
            bigger.pop(0)        # 赋值后A,B会随着bigger的改变而改变
        return res

    ans = [0] * k
    for i in range(k + 1):       # 遍历k种情况,找出最大的值
        if i <= len(nums1) and k - i <= len(nums2):
            ans = max(ans, merge(pick_k_max(nums1, i), pick_k_max(nums2, k - i)))
    return ans

#算法测试
if __name__ == '__main__':
    result=nums(6)
    nums1=result[0]
    nums2=result[1]
    print(nums1)
    print(nums2)
    print(maxNumber(nums1,nums2,5))

"""
测试结果：
[5, 5, 3, 1, 2, 6]
[9, 5, 1, 2]
[[9, 6, 5, 1, 2], 0.06850000000002687]
"""